The present invention relates to specialized electronic devices for looking up data such as may be used in high-speed network routers and switches and, in particular, to a device that may optimize its memory topology for different lookup tasks.
Computer networks allow the exchange of data among spatially separated computers connected by “links”, the latter physically implemented as electrical conductors, fiber optics, and radio waves. The dominant network protocols work by dividing a data message into data packets, each of which contains a destination address. The destination address attached to the packets permits the packets to navigate through complex and dynamically changing networks to the destination. When particular links used by a message become crowded or disabled, packets of that message, guided by the destination address, may be routed through different links to reach their destination in a manner invisible to the sender.
A key element in implementing a network using addressed packets is a device called a router (or sometimes a switch) which reads packets' addresses and steers them according to the addresses among the different links joined by the router. For this purpose, the router employs a “routing table” matching packet addresses with ports leading to the different links. The data in the router table maybe manually programmed or may be “learned” using various router heuristics.
Routers may also perform other tasks such as address translation where the packet addresses change for another packet address, or the management of white or blacklists where certain packets may be blocked, for example, to prevent denial of service attacks where the network is flooded with spurious packets from a given address.
All of these functions of a router require the router to look up packet addresses or other packet features in memory, and to perform these operations repeatedly and rapidly. The effectiveness of a router is largely a function of how quickly these memory lookups may be completed.
The memory lookup function may be implemented by a conventional processor reading a table implemented in random access memory. Such memories allow data to be read from identified memory addresses when the address is provided. Finding data with such an architecture requires searching through multiple addresses, a generally time-consuming process. For this reason, high performance routers may use so-called ternary content addressable memories (TCAM) which allow the entire memory to be searched in parallel for the data of interest. These memories substantially reduce the time taken for the memory lookups but are costly and consume considerable power and concomitantly generate greater amounts of heat. Both electrical usage and heat generation can be problems in large data centers.
A possible solution to the problems attendant to rapid memory lookup is the creation of specialized electrical hardware for this purpose. This task, however, is complicated by the variety of different lookup tasks that may be required in a modern router and the need to employ the router in an evolving set of network tasks. For example, currently routers may need to respond to both Internet Protocol (IP) address lookups and local area network (Ethernet-type) lookups. An IP address lookup deals with addresses that have topological significance, that is, different portions of the address represent different networks and sub networks. For IP address lookups, a tree structure may be preferred as the tree allows successively parsing the network address in a manner that reflects the network topology. In contrast, for Ethernet-type lookups the address will typically have no topological significance, representing simply an arbitrary unique number assigned to each device. In this case, the memory lookups are better implemented using a hash table which encodes no topological information about the addresses stored and allows a simpler lookup operation.
As networks grow more complicated and routers are called upon to execute additional tasks, it is likely that current methods for processing packets will prove sub-optimal and changes to the data structures used by routers during packet processing will be needed. Current methods of packet processing may also be sub-optimal for new protocols, extensions to existing protocols, or the introduction of new features for packet processing.
U.S. Pat. No. 7,940,755 entitled “Lookup Engine with Programmable Memory Topology” assigned to the same assignee as the present invention and hereby incorporated by reference, describes a novel computer architecture that flexibly addresses the conflicting goals of high-speed memory operations and the flexibility inherent in reprogrammable hardware. In this design multiple inter-communicating “tiles” are each associated with portions of lookup memory. A variety of different types of lookup tasks may be implemented by programming the individual tiles and a path of intercommunication data among the tiles. This latter programmability allows different architectural topologies to be created that are optimized for different types of lookup tasks.
Each of the tiles may be associated with a von Neumann type processor that may implement a multistep program for processing the data it receives from other tiles (or from a general-purpose processor) and then may pass that data after processing to another tile (or back to the general-purpose processor). In a typical program, data will be passed in a chain between multiple tiles before returning to the general-purpose processor.